package previous.Test_0312;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //图像渲染
    int[]  dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        //刚开始的颜色
          int prev=image[sr][sc];
          //处理边界情况
        if(prev==color) return image;
        int m=image.length;
        int n=image[0].length;
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{sr,sc});
        while(!q.isEmpty()){
            int[] t=q.poll();
            int a=t[0];
            int b=t[1];
            image[a][b]=color;
            for (int i = 0; i < 4; i++) {
                int x=dx[i]+a;
                int y=dy[i]+b;
                if(x>=0 && x<m && y>=0 && y<n && prev==image[x][y]){
                    q.add(new int[]{x,y});
                }
            }
        }
        return image;
    }
    //岛屿数量
    public int numIslands(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        Queue<int[]> q=new LinkedList<>();
        int count=0;
        boolean[][] vis=new boolean[301][301];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <n ; j++) {
                if(vis[i][j]==false && grid[i][j]=='1'){
                    count++;
                    vis[i][j]=true;
                    q.add(new int[]{i,j});
                    while(!q.isEmpty()){
                       int t[]=q.poll();
                       int a=t[0];
                       int b=t[1];
                        for (int k = 0; k < 4; k++) {
                            int x=dx[k]+a;
                            int y=dy[k]+b;
                            if(x>=0 && x<m && y>=0 && y<n && vis[x][y]==false && grid[x][y]=='1'){
                                q.add(new int[]{x,y});
                                vis[x][y]=true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
    //岛屿的最大面积
    int ret=0;
    public int maxAreaOfIsland(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        boolean[][] vis=new boolean[m][n];
        Queue<int[]> q=new LinkedList<>();

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!vis[i][j] && grid[i][j]==1){
                    int count=0;
                    vis[i][j]=true;
                    q.add(new int[]{i,j});
                    while(!q.isEmpty()){
                        count++;
                        int[] t=q.poll();
                        int a=t[0];
                        int b=t[1];
                        for(int k=0;k<4;k++){
                            int x=dx[k]+a;
                            int y=dy[k]+b;
                            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y]==1){
                                q.add(new int[]{x,y});
                                vis[x][y]=true;
                            }
                        }
                        ret= Math.max(ret,count);
                    }
                }
            }
        }
        return ret;
    }
    //被围绕的区域
    int m;
    int n;
    public void solve(char[][] board) {
          m=board.length;
          n=board[0].length;
          Queue<int[]> q=new LinkedList<>();
          //处理第一行和最后一行
        for (int i = 0; i < n; i++) {
            if(board[0][i]=='O'){
                q.add(new int[]{0,i});
            dfs(0,i,board,q);
            }
            if(board[m-1][i]=='O'){
                q.add(new int[]{m-1,i});
            dfs(m-1,i,board,q);
            }
        }
        for (int j = 0; j < m; j++) {
            if(board[j][0]=='O'){
                q.add(new int[]{j,0});
            dfs(j,0,board,q);
            }
            if(board[j][n-1]=='O'){
                q.add(new int[]{j,n-1});
            dfs(j,n-1,board,q);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j]=='O') board[i][j]='X';
                if(board[i][j]=='.') board[i][j]='O';
            }
        }
    }
    public void dfs(int i,int j,char[][] board ,Queue<int[]> q ){
        board[i][j] = '.';
        q.add(new int[]{i, j});
        while(!q.isEmpty()){
            int[] t=q.poll();
            int a=t[0];
            int b=t[1];
            for (int k = 0; k < 4; k++) {
                 int x=dx[k]+a;
                 int y=dy[k]+b;
                if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O'){
                     board[x][y]='.';
                     q.add(new int[]{x, y});
            }
        }
        }
    }
}
